//
// Created by Administrator on 2025/8/6.
//

#ifndef SINGLECIRCLELIST_H
#define SINGLECIRCLELIST_H

namespace circleList_single {
    struct Node {
        explicit Node(const int data = 0)
            : data_(data)
              , next_(nullptr) {
        }

        int data_;
        Node *next_;
    };

    class iterator {
    public:
        explicit iterator(Node *ptr = nullptr)
            : ptr_(ptr) {
        }

        void operator++() {
            ptr_ = ptr_->next_;
        }

        bool operator!=(const iterator &other) const {
            return ptr_ != other.ptr_;
        }

        int operator*() const {
            return ptr_->data_;
        }

    private:
        Node *ptr_;
    };

    class singleCircleList {
    public:
        //构造函数
        explicit singleCircleList() {
            head_ = new Node();
            tail_ = head_;
            head_->next_ = head_;
        }

        //析构函数
        ~singleCircleList() {
            //没有头的时候就不用析构了
            if (head_ == nullptr) {
                return;
            }
            // 从头节点开始，遍历链表，删除每个节点
            const Node *p = head_->next_;
            while (p != head_) {
                // 将头节点的next指针指向当前节点的next节点
                head_->next_ = p->next_;
                // 删除当前节点
                delete p;
                // 将p指向下一个节点
                p = head_->next_;
            }
            // 删除头节点
            delete head_;
            // 将头节点指针置为空
            head_ = nullptr;
        }

        // 插入节点
        void insertNode(const int val) {
            // 创建新节点
            auto p = new Node(val);
            // 将尾节点的next指针指向新节点
            tail_->next_ = p;
            // 将尾节点指向新节点
            tail_ = p;
            // 将尾节点的next指针指向头节点，形成循环链表
            tail_->next_ = head_;
        }

        // 向链表头部插入节点
        void headInsertNode(const int val) {
            // 创建新节点
            auto p = new Node(val);
            // 将新节点的next指向头节点的next
            p->next_ = head_->next_;
            head_->next_ = p;
            if (tail_ == head_) {
                tail_ = p;
            }
        }

        // 删除指定值的节点
        void deleteNode(const int val) {
            // 定义一个指针p指向头节点的下一个节点
            auto p = head_->next_;
            // 定义一个指针pre指向头节点
            auto pre = head_;
            // 遍历链表，直到p指向头节点
            while (p != head_) {
                // 如果p指向的节点的值等于指定值
                if (p->data_ == val) {
                    // 将pre节点的next指针指向p节点的下一个节点
                    pre->next_ = p->next_;
                    // 如果p指向的节点是尾节点
                    if (p == tail_) {
                        // 将尾节点指向pre节点
                        tail_ = pre;
                    }
                    delete p;
                    p = nullptr;
                    break;
                } else {
                    // 否则，将pre指针指向p节点
                    pre = p;
                    // 将p指针指向下一个节点
                    p = p->next_;
                }
            }
        }

        // 删除所有值为val的节点
        void deleteAllNode(const int val) {
            // 定义指针p，指向head_的下一个节点
            auto p = head_->next_;
            // 定义指针pre，指向head_
            auto pre = head_;
            // 当p不等于head_时，循环执行
            while (p != head_) {
                // 如果p指向的节点的值为val
                if (p->data_ == val) {
                    // 将pre的next_指向p的next_
                    pre->next_ = p->next_;
                    // 如果p指向的是tail_
                    if (p == tail_) {
                        // 将tail_指向pre
                        tail_ = pre;
                    }
                    // 删除p指向的节点
                    delete p;
                    // 将p指向pre的next_
                    p = pre->next_;
                } else {
                    // 否则，将pre指向p
                    pre = p;
                    // 将p指向p的next_
                    p = p->next_;
                }
            }
        }

        // 判断链表是否为空
        bool isEmpty() const {
            return head_ == nullptr || head_->next_ == head_;
        }

        // 获取链表长度
        int getLength() const {
            // 初始化长度为0
            int length = 0;
            // 获取头节点的下一个节点
            auto p = head_->next_;
            // 遍历链表，直到到达尾节点
            while (p != head_) {
                // 长度加1
                ++length;
                // 移动到下一个节点
                p = p->next_;
            }
            // 返回链表长度
            return length;
        }

        // 查找链表中是否存在值为val的节点
        bool find(const int val) const {
            // 定义指针p，指向头节点的下一个节点
            auto p = head_->next_;
            // 如果头节点的下一个节点为空，则返回false
            if (p == nullptr) {
                return false;
            }
            // 遍历链表，直到p指向头节点
            while (p != head_) {
                // 如果p指向的节点的值为val，则返回true
                if (p->data_ == val) {
                    return true;
                }
                // 否则，p指向下一个节点
                p = p->next_;
            }
            // 遍历完整个链表，仍未找到值为val的节点，则返回false
            return false;
        }

        //约瑟夫环问题的解决，这个问题的描述是(在一个环形链表中，从第N个链表元素开始，每隔k个节点删除一个节点，直到链表中只剩下一个节点为止)
        void josephus(const int n, const int k) {
            //判断这个链表是不是空
            if (isEmpty()) {
                return;
            }
            showList();
            //定义一个指针p指向第n个节点
            auto p = head_->next_;
            auto q = head_;
            for (int i = 1; i < n; i++) {
                p = p->next_;
                if (p == head_) {
                    p = p->next_;
                }
            }
            //定义一个指针q指向p的前一个节点
            while (q->next_ != p) {
                q = q->next_;
            }
            //开始删除节点
            while (q != p) {
                for (int i = 1; i < k; i++) {
                    p = p->next_;
                    q = q->next_;
                    //如果p指向头结点，则将p指向下一个节点，q指向下一个节点,主要是去掉头节点
                    if (p == head_) {
                        p = p->next_;
                        q = q->next_;
                    }
                }
                //将q的next指向p的next
                q->next_ = p->next_;
                //输出p的数据
                std::cout << p->data_ << " ";
                //删除p
                delete p;
                //将p指向q的next
                p = q->next_;
                if (p == head_ && q != p) {
                    p = p->next_;
                    q = q->next_;
                }
                if (p == head_ && p == q) {
                    delete p;
                    p = nullptr;
                    q = nullptr;
                    head_ = nullptr;
                }
            }
        }

        //约瑟夫环问题的重写
        void josephus2(const int start, const int k) {
            //判断这个链表是不是空
            if (isEmpty()) {
                return;
            }
            //非空的处理方式
            const Node *cur = head_->next_;
            //找到开始的节点
            for (int i = 1; i < start; i++) {
                cur = cur->next_;
                if (cur == head_) {
                    cur = cur->next_;
                }
            }
            //确定cur不是头节点
            if (cur == head_)
                cur = cur->next_;
            //找到cur的上一个节点
            Node *pre = head_;
            while (pre->next_ != cur) {
                pre = pre->next_;
            }
            while (cur != pre) {
                //开始找到这个cur后的K个节点
                for (int i = 1; i < k; i++) {
                    cur = cur->next_;
                    pre = pre->next_;
                    //如果cur指向头节点，则将cur指向下一个节点，pre指向下一个节点
                    if (cur == head_) {
                        cur = cur->next_;
                        pre = pre->next_;
                    }
                }
                //找到要删除的节点 开始删除
                pre->next_ = cur->next_;
                std::cout << cur->data_ << " ";
                delete cur;
                cur = pre->next_;
                if (cur == head_ && pre != cur) {
                    cur = cur->next_;
                    pre = pre->next_;
                }
                if (cur == head_ && pre == cur) {
                    delete cur;
                    cur = nullptr;
                    pre = nullptr;
                    head_ = nullptr;
                }
            }
        }

        iterator begin() {
            return iterator(head_->next_);
        }

        iterator end() {
            return iterator(tail_->next_);
        }

        //展示链表
        void showList() const {
            if (isEmpty()) {
                return;
            }
            auto p = head_->next_;
            while (p != head_) {
                std::cout << p->data_ << " ";
                p = p->next_;
            }
            std::cout << std::endl;
        }

    private:
        Node *head_; //头节点
        Node *tail_; //尾节点
    };
} // circle list_single

#endif //INTELLECTUALISING_H
